perms([],T,R,[T|R]).
perms([X|Xs],T,R):-cycle([],X,Xs,T,R).

cycle(L,M,[],T,R):-perms(L,[M|T],R).
cycle(L,M,[R|RR],T,P):-
  append(L,R,LR),
  perms(LR,[M|T], R),
  cycle([M|L],R,RR,T,P).

fperms(Xs,Ps):-perms(Xs,[],[],Ps).

go:-fperms([1,2,3],Xs),write(Xs),nl,fail.

/*


Although your automatic programming system sounds interesting, that
conclusion would be a bit premature.  Here's another program for
generating permutations:

fun perms ([],    tail, res) = tail :: res
  | perms (x::xr, tail, res) = cycle([], x, xr, tail, res)
and cycle (left, mid, [],             tail, res) = 
    perms(left, mid::tail, res)
  | cycle (left, mid, right as r::rr, tail, res) = 
    cycle(mid::left, r, rr, tail, perms(left @ right, mid::tail, res))

fun fastperms xs = perms(xs, [], [])

(* The idea is to build the permutations from the tail rather than the
 * head of the list; and to use an accumulating parameter for the
 * resulting list of permutations; both reduce the number of cons
 * operations.  
 *
 * perms(xs, tail, res) = map (fn pm => pm @ tail) xs_perms @ res
 * where xs_perms is a list of permutations of xs
*)

The programs compare as follows under SML/NJ 108.18 (on a Linux/133MHz
Pentium):

(1) The permutation algorithm generated by adate:

    time (length o f) [1,2,3,4,5,6,7,8,9];
    User: 34.600  System: 3.920  GC: 27.780  Real: 40.425
    Memory: 39 MB resident

(2) The above program:

    time (length o fastperms) [1,2,3,4,5,6,7,8,9];
    User: 11.700  System: 1.240  GC: 8.460  Real: 13.743
    Memory: 18 MB resident


I have received five permutation programs by e-mail. Asymptotically, the
program written by Peter Sestoft seems to be the fastest.

Rewritten into the ADATE subset of ML, this program is as follows.

fun f(Xs) = 
  let
    fun perms(As,Tail,Res) =
      case As of
        nil => Tail::Res
      | X::Xr => cycle(nil, X, Xr, Tail, Res)
    and cycle(Left, Mid, Right, Tail1, Res1) =
      case Right of
        nil => perms(Left,Mid::Tail1,Res1)
      | R::Rr => 
          cycle(Mid::Left, R, Rr, Tail1, perms(Left@Right, Mid::Tail1, Res1))
  in
    perms(Xs, nil, nil)
  end


*/
